package code.oldCode.classic150;


import java.util.*;

/**
 * @author cuihaoran
 * @date 2024/10/21
 */
public class Classic150_array {

    /* 88. 合并两个有序数组 */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // len(nums1) = m + n
        int[] num = new int[m];
        System.arraycopy(nums1, 0, num, 0, m);
        int i = 0, j = 0, k = 0;
        while (i < m && j < n) {
            if (num[i] <= nums2[j]) {
                nums1[k] = num[i];
                i++;
            } else {
                nums1[k] = nums2[j];
                j++;
            }
            k++;
        }
        while (i < m) {
            nums1[k] = num[i];
            i++;
            k++;
        }
        while (j < n) {
            nums1[k] = nums2[j];
            j++;
            k++;
        }
    }

    /* 27. 移除元素 */
    public int removeElement(int[] nums, int val) {
        if (nums.length == 0)
            return 0;
        // nums 的前面保留剩下的元素，且return剩下的个数
        int len = nums.length;
        // 保证pos左面都是保留的元素
        int pos = 0, last = len - 1;
        while (last >= 0 && nums[last] == val)
            last--;
        while (pos <= last) {
            if (nums[pos] == val) {
                int temp = nums[pos];
                nums[pos] = nums[last];
                nums[last] = temp;
                while (last >= pos && nums[last] == val)
                    last--;
            }
            pos++;
        }
        return pos;
    }

    /* 力扣官方题解
    https://leetcode.cn/problems/remove-element/solutions/730203/yi-chu-yuan-su-by-leetcode-solution-svxi/ */
    public int removeElement_leetcode(int[] nums, int val) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }

    /* 26. 删除有序数组中的重复项 */
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        int left = 0, right = 1;
        while (right < len) {
            if (nums[left] != nums[right]) {
                left++;
                nums[left] = nums[right];
            }
            right++;
        }
        return left + 1;
    }

    /* 80. 删除有序数组中的重复项 II */
    public int removeDuplicates2(int[] nums) {
        int len = nums.length;
        int update = 1;
        int now_length = 1;
        for (int i = 1; i < len; i++) {
            // 两个相等
            if (nums[i] == nums[i - 1]) {
                now_length++;
                if (now_length <= 2) {
                    nums[update] = nums[i];
                    update++;
                }
            }
            // 两个不相等
            else {
                now_length = 1;
                nums[update] = nums[i];
                update++;
            }
        }
        return update;
    }

    /* 169. 多数元素 */
    public int majorityElement(int[] nums) {
        // 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
        // Boyer-Moore 算法
        int count = 0;
        int mNumber = 0;
        int len = nums.length;
        for (int num : nums) {
            if (count == 0) {
                mNumber = num;
                count++;
            } else {
                if (mNumber == num) {
                    count++;
                } else {
                    count--;
                }
            }
        }
        return mNumber;
    }

    /* 189. 轮转数组 */
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        int[] tempNums = new int[len];
        System.arraycopy(nums, 0, tempNums, 0, len);
        for (int i = 0; i < len; i++) {
            nums[(i + k) % len] = tempNums[i];
        }
    }

    /* 官解方法，数组翻转，空间复杂度缩小至O(1)
    https://leetcode.cn/problems/rotate-array/solutions/551039/xuan-zhuan-shu-zu-by-leetcode-solution-nipk/?envType=study-plan-v2&envId=top-interview-150 */
    public void rotate_leetcode(int[] nums, int k) {
        int len = nums.length;
        k %= len;
        reverse(nums, 0, len - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, len - 1);
    }

    private void reverse(int[] nums, int begin, int end) {
        while (begin < end) {
            int temp = nums[begin];
            nums[begin] = nums[end];
            nums[end] = temp;
            begin++;
            end--;
        }
    }

    /* 121. 买卖股票的最佳时机 */
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[] buy = new int[len]; // 在前i天买获得的最大利润
        int[] sell = new int[len]; // 在前i天卖获得的最大利润
        buy[0] = -prices[0];
        sell[0] = 0;
        for (int i = 1; i < len; i++) {
            buy[i] = Math.max(buy[i - 1], -prices[i]);
            sell[i] = Math.max(sell[i - 1], buy[i] + prices[i]);
        }
        return sell[len - 1];
    }

    /* 122. 买卖股票的最佳时机 II */
    public int maxProfit_2(int[] prices) {
        int len = prices.length;
        int[] with = new int[len];
        int[] without = new int[len];
        with[0] = -prices[0];
        without[0] = 0;
        for (int i = 1; i < len; i++) {
            with[i] = Math.max(with[i - 1], without[i - 1] - prices[i]);
            without[i] = Math.max(without[i - 1], with[i - 1] + prices[i]);
        }
        return Math.max(with[len - 1], without[len - 1]);
    }

    /* 55. 跳跃游戏 */
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int farest = 0;
        for (int i = 0; i < len; i++) {
            farest = Math.max(farest, i + nums[i]);
            if (i == farest && i != len - 1)
                return false;
        }
        return true;
    }

    /* 45. 跳跃游戏 II */
    public int jump(int[] nums) {
        // 一般的动态规划，并非最优 O(n^2)
        int len = nums.length;
        int[] dp = new int[len]; // dp[i] 表示跳到i的最小跳跃次数 dp[i] = Min(dp[能跳到i的所有节点]) + 1
        dp[0] = 0;
        for (int i = 1; i < len; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i) {
                    min = Math.min(min, dp[j]);
                }
            }
            dp[i] = min + 1;
        }
        return dp[len - 1];
    }

    /* 贪心，O(n) */
    public int jump_On(int[] nums) {
        int len = nums.length;
        int farest = 0;
        int jump = 0;
        int current_end = 0;
        for (int i = 0; i < len - 1; i++) {
            farest = Math.max(farest, i + nums[i]);
            if (i == current_end) {
                jump++;
                current_end = farest;
            }
        }
        return jump;
    }

    /* 274. H 指数 */
    public int hIndex(int[] citations) {
        int len = citations.length;
        int[] hash = new int[len + 1]; // hash[i] 表示被至少引用i次的文章
        for (int i = 0; i < len; i++) {
            if (citations[i] > len)
                citations[i] = len;
            for (int j = 0; j <= citations[i]; j++) {
                hash[j]++;
            }
        }
        int h = 0;
        for (int i = 0; i <= len; i++) {
            if (hash[i] >= i)
                h = i;
        }
        return h;
    }

    /* 先排序 O(n*logn) */
    public int hIndex_(int[] citations) {
        int len = citations.length;
        int h = 0;
        // 排序
        Arrays.sort(citations);
        for (int i = 0; i < len; i++) {
            // 如果长度大于值，取值
            if (len - i >= citations[i]) {
                h = citations[i];
            }
            // 如果值大于长度，取max(h, 长度)
            else {
                h = Math.max(h, len - i);
            }
        }
        return h;
    }

    /* 238. 除自身以外数组的乘积 */
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] left = new int[len];
        int[] right = new int[len];
        int[] ans = new int[len];
        left[0] = 1;
        right[len - 1] = 1;
        for (int i = 1; i < len; i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }
        for (int i = len - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }
        for (int i = 0; i < len; i++) {
            ans[i] = left[i] * right[i];
        }
        return ans;
    }

    /* 134. 加油站 */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // 先尝试模拟, 超时
        int len = gas.length;
        // 尝试每一个位置
        for (int i = 0; i < len; i++) {
            // 如果 gas[i] < cost[i] , 说明这个起始位置不行
            if (gas[i] < cost[i])
                continue;
            // 尝试走一圈
            int pos = i; // 起始位置
            int step = len; // 剩余步数
            int tank = 0; // 剩余油量
            while (step > 0) {
                tank += gas[pos];
                tank -= cost[pos];
                // 如果 tank < 0 结束
                if (tank < 0)
                    break;
                step--;
                pos = (pos + 1) % len;
            }
            // 成功
            if (step == 0)
                return i;
        }

        return -1;
    }

    /* 134. 加油站——贪心*/
    public int canCompleteCircuit_tanxin(int[] gas, int[] cost) {
        // 贪心，如果从x出发到了y，不能到y+1，那么说明从[x,y]出发都到不了y+1，下次直接从y+1开始
        int len = gas.length;
        int i = 0;
        while (i < len) {
            int pos = i;
            int step = 0;
            int tank = 0;
            while (step < len) {
                tank += gas[pos];
                tank -= cost[pos];
                if (tank < 0)
                    break;
                step++;
                pos = (pos + 1) % len;
            }
            if (step == len)
                return i;
            else
                i = i + step + 1;
        }
        return -1;
    }

    /* 13. 罗马数字转整数 */
    public int romanToInt(String s) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        hashMap.put('I', 1);
        hashMap.put('V', 5);
        hashMap.put('X', 10);
        hashMap.put('L', 50);
        hashMap.put('C', 100);
        hashMap.put('D', 500);
        hashMap.put('M', 1000);
        int ans = 0;
        int lastValue = 0, nowValue = 0;
        int len = s.length();
        for (int i = len - 1; i >= 0; i--) {
            Character c = s.charAt(i);
            nowValue = hashMap.get(c);
            if (nowValue >= lastValue)
                ans += nowValue;
            else
                ans -= nowValue;
            lastValue = nowValue;
        }
        return ans;
    }

    /* 12. 整数转罗马数字 */
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuffer roman = new StringBuffer();
        for (int i = 0; i < values.length; ++i) {
            int value = values[i];
            String symbol = symbols[i];
            while (num >= value) {
                num -= value;
                roman.append(symbol);
            }
            if (num == 0) {
                break;
            }
        }
        return roman.toString();
    }

    /* 58. 最后一个单词的长度 */
    public int lengthOfLastWord(String s) {
        int len = s.length();
        int ans = 0;
        boolean over = false;
        for (int i = len - 1; i >= 0; i--) {
            if (s.charAt(i) != ' ') {
                over = true;
                ans++;
            } else {
                if (over)
                    break;
            }
        }
        return ans;
    }

    /* 14. 最长公共前缀 */
    public String longestCommonPrefix(String[] strs) {
        // 如果strs.length == 1，直接返回
        int strsLen = strs.length;
        if (strsLen == 1)
            return strs[0];

        int minLen = Integer.MAX_VALUE;
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < strsLen; i++) {
            minLen = Math.min(minLen, strs[i].length());
        }

        for (int i = 0; i < minLen; i++) {
            boolean isEqual = true;
            for (int j = 1; j < strsLen; j++) {
                if (strs[j].charAt(i) != strs[j - 1].charAt(i)) {
                    isEqual = false;
                    break;
                }
            }
            if (isEqual)
                sb.append(strs[0].charAt(i));
            else
                break;
        }
        return sb.toString();
    }

    /* 151. 反转字符串中的单词 */
    public String reverseWords(String s) {
        // 去除前导、后导空格
        s = s.trim();
        // 去除单词中空格
        int len = s.length();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) != ' ' || s.charAt(i) == ' ' && s.charAt(i - 1) != ' ')
                sb.append(s.charAt(i));
        }
        // 反转
        String string = sb.toString();
        char[] chars = string.toCharArray();
        len = chars.length;
        int start = 0;
        for (int i = 0; i < len; i++) {
            if (chars[i] == ' ') {
                reverse(chars, start, i - 1);
                start = i + 1;
            } else if (i == len - 1) {
                reverse(chars, start, i);
            }
        }
        reverse(chars, 0, len - 1);

        return new String(chars);
    }

    private void reverse(char[] c, int start, int end) {
        while (start < end) {
            char temp = c[start];
            c[start] = c[end];
            c[end] = temp;
            start++;
            end--;
        }
    }

    /* 6. Z 字形变换 */
    public String convert(String s, int numRows) {
        int len = s.length();
        List<Character>[] lists = new List[numRows];
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            lists[i] = new ArrayList<>();
        }
        for (int i = 0; i < len; i++) {
            int pos = getPos(i, numRows);
            lists[pos].add(s.charAt(i));
        }
        for (int i = 0; i < numRows; i++) {
            for (Character c : lists[i]) {
                sb.append(c);
            }
        }
        return sb.toString();
    }

    private int getPos(int pos, int numRows) {
        // 一轮 5~8 4~6 3~4 2~2 n~(2n-2)
        if (numRows == 1)
            return 0;
        pos = pos % (2 * numRows - 2);
        if (pos < numRows) {
            return pos;
        } else {
            return (numRows - 1) - (pos - (numRows - 1));
        }
    }

    /* 28. 找出字符串中第一个匹配项的下标 */
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }

    /* 28. 找出字符串中第一个匹配项的下标 KMP */
    public int strStr_KMP(String haystack, String needle) {
        // needle为空，返回0
        if (needle.isEmpty())
            return 0;
        // 获取next数组
        int[] next = buildNext(needle);
        // 遍历haystack
        int j = 0; // needle当前匹配位置
        for (int i = 0; i < haystack.length(); i++) {
            // 如果不匹配，则返回到next[j]
            while (j > 0 && haystack.charAt(i) != needle.charAt(j))
                j = next[j - 1];
            // 如果匹配，j+1
            if (haystack.charAt(i) == needle.charAt(j))
                j++;
            // 如果j匹配完了，返回结果
            if (j == needle.length())
                return i - j + 1;
        }

        return -1;
    }

    // 辅助方法，用于构建子串的部分匹配表（next 数组）
    private int[] buildNext(String needle) {
        int[] next = new int[needle.length()];
        // 遍历needle，构造next数组
        int j = 0;
        for (int i = 1; i < needle.length(); i++) {
            // 如果不匹配，则返回到next[j]
            while (j > 0 && needle.charAt(i) != needle.charAt(j))
                j = next[j - 1];
            // 如果匹配，j+1
            if (needle.charAt(i) == needle.charAt(j))
                j++;
            // j为next[i]的值
            next[i] = j;
        }

        return next;
    }


    /* 135. 分发糖果 */
    public int candy(int[] ratings) {
        // [1,3,2,2,1] -> 7
        // [1,2,1,2,1] √
        // [1,2,87,87,87,2,1] -> 13
        // [1,2, 3, 1, 3,2,1] √
        // [1,6,10,8,7,3,2] -> 18
        // [1,2, 5,4,3,2,1]
        // [1,3,4,5,2] -> 11
        // [1,2,3,4,1]
        int len = ratings.length;
        // 每个孩子至少一个
        int[] nums = new int[len];
        Arrays.fill(nums, 1);
        // 相邻不同，加一个：正反各一遍
        for (int i = 1; i < len; i++) {
            if (ratings[i] > ratings[i - 1] && nums[i] <= nums[i - 1])
                nums[i] = nums[i - 1] + 1;
        }
        for (int i = len - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1] && nums[i] <= nums[i + 1])
                nums[i] = nums[i + 1] + 1;
        }

        return Arrays.stream(nums).sum();
    }

    /* 42. 接雨水 */
    public int trap(int[] height) {
        int len = height.length;
        int[] leftMax = new int[len];
        int[] rightMax = new int[len];
        int ans = 0;
        leftMax[0] = height[0];
        rightMax[len - 1] = height[len - 1];
        for (int i = 1; i <= len - 1; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        for (int i = len - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        for (int i = 0; i < len; i++) {
            ans += Math.max(Math.min(leftMax[i], rightMax[i]) - height[i], 0);
        }
        return ans;
    }

    /* 68. 文本左右对齐 */
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> list = new ArrayList<>();
        int right = 0; // 遍历到单词的位置
        // 每一行一个循环
        while (true) {
            int left = right; // 当前行的起始位置
            int nowLen = 0; // 当前单词长度之和
            // 确定当前行能放多少单词
            while (right < words.length && nowLen + words[right].length() + right - left <= maxWidth) {
                nowLen += words[right].length();
                right++;
            }
            // 当前为最后一行（当前行遍历到最后一个单词），左对齐，并退出循环
            if (right == words.length) {
                StringBuilder sb = join(words, left, right, blank(1));
                sb.append(blank(maxWidth - sb.length()));
                list.add(sb.toString());
                return list;
            }
            // 当前行只有一个单词
            if (right - left == 1) {
                StringBuilder sb = join(words, left, right, blank(1));
                sb.append(blank(maxWidth - sb.length()));
                list.add(sb.toString());
            }
            // 当前行有多个单词
            else {
                int numWords = right - left;
                int numBlanks = maxWidth - nowLen;
                int avg = numBlanks / (numWords - 1); // 平均每个单词之间的空格数
                int last = numBlanks % (numWords - 1); // 多出来几个空格
                StringBuilder sb = new StringBuilder();
                sb.append(join(words, left, left + last + 1, blank(avg + 1)));
                sb.append(blank(avg));
                sb.append(join(words, left + last + 1, right, blank(avg)));
                list.add(sb.toString());
            }
        }
    }

    private String blank(int n) { // 返回长度为n的空格String
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(' ');
        }
        return sb.toString();
    }

    private StringBuilder join(String[] words, int left, int right, String sep) { // 返回[left, right)加sep隔开的sb
        StringBuilder sb = new StringBuilder(words[left]);
        for (int i = left + 1; i < right; i++) {
            sb.append(sep);
            sb.append(words[i]);
        }
        return sb;
    }

    public static void main(String[] args) {
        Classic150_array classic150Part1 = new Classic150_array();
    }

}
